//抖音上的丛林迷宫游戏
//block定义:
// 0: 空地，会跌落
// 1: 绿地
// *: 目标地
// A: 蜗牛(移动对象)
// B: 蜘蛛(移动对象)
// C: 蚂蚱(移动对象)
// D: 瓢虫(移动对象)
// E: 蜜蜂(移动对象)
// F: 蝴蝶(移动对象)
// G: 甲虫(移动对象)

//动物移动到目标地，就会消失，同时目标地变绿地

var clmg_index = 0; //当前节点索引  

// 导入 baseNode
import { baseNode } from './bfsAsync.js';

// 修正 ClmgFactory 继承自 baseNode
function ClmgFactory(width,height,stepLimit) {
    // 调用父类构造函数初始化 parent 和 actionDesc
    baseNode.call(this);
    this.width = width;
    this.height = height;
    this.step_limit = stepLimit; //步数限制
    this.oldboard = []; //旧棋盘描述
    this.board = []; //棋盘描述
    this.barriers = []; //障碍物列表
    this.current_step = 0; //当前步数
    this.index = clmg_index++; //当前节点索引
    //this.normalize = []; //归一化棋盘(在这里其实不是归一化，是唯一标识)
}

// 设置原型链
ClmgFactory.prototype = Object.create(baseNode.prototype);
ClmgFactory.prototype.constructor = ClmgFactory;

//拷贝节点
ClmgFactory.prototype.CopyFrom = function(node)
{
    this.width = node.width;
    this.height = node.height;
    this.step_limit = node.step_limit;
    this.current_step = node.current_step;
    // 对board二维字符数组进行深拷贝
    this.board = [];
    for (let i = 0; i < node.board.length; i++) {
        // 对每一行也进行深拷贝
        this.board[i] = node.board[i].slice();
    }
    // 对oldboard二维字符数组进行深拷贝
    this.oldboard = [];
    for (let i = 0; i < node.board.length; i++) {
        // 对每一行也进行深拷贝
        this.oldboard[i] = node.board[i].slice();
    }
    
    // 对barriers数组也进行深拷贝
    this.barriers = [];
    for (let i = 0; i < node.barriers.length; i++) {
        this.barriers[i] = node.barriers[i].slice();
    }
}

//转为成功的结束状态
ClmgFactory.prototype.success = function()
{
    this.current_step = this.step_limit;
    for (let x = 0; x < this.width; x++)
    {
        for (let y = 0; y < this.height; y++)
        {
            if (this.board[y][x] == '*') {
                this.board[y][x] = '1';
            }
            //动物消失
            else if (this.isMovableObj(x,y)) {
                this.board[y][x] = '1';
            }
        }
    }
}



//从json文件中读取棋盘描述，文件内容为json,格式如下:
// {
//     "width": 5,
//     "height": 5,
//     "step_limit": 10,
//     "board": [
//         "00100",
//         "00100",
//         "00**0",
//         "00A00",
//         "0BB00"
//     ],
//     "barriers": [
//         [0,0,0,1],
//         [0,1,0,2],
//         [0,2,0,3],
//         [0,3,0,4]
//     ]
// }
ClmgFactory.prototype.readFromJson = function(jsonText)
{
    let initJson = JSON.parse(jsonText);
    //校验棋盘描述
    for (let row of initJson.board)
    {
        if (row.length != initJson.width) {
            return false;
        }
    }
    //校验障碍物描述
    for (let barrier of initJson.barriers) {
        if (barrier.length != 4) {
            return false;
        }
    }
    this.width = initJson.width;
    this.height = initJson.height;
    this.step_limit = initJson.step_limit;
    this.current_step = 0;
    //initJson.board为字符串列表，需要转换为字符数组列表
    //将字符串转换为字符数组
    for (let i = 0; i < initJson.board.length; i++) {
        initJson.board[i] = initJson.board[i].split('');
    }
    this.board = [...initJson.board];
    this.barriers = [...initJson.barriers];
    return true;
}

//初始化棋盘
//_board为字符串列表
ClmgFactory.prototype.initBoard = function(_board)
{
    if (_board.length != this.height) {
        return false;
    }
    for (let row of _board)
    {
        if (row.length != this.width) {
            return false;
        }
    }
    this.board = [..._board];
    //this.normalize = this.normalizeBoard(this.board);
    return true;
}

//增加障碍物
//_barrier为[x1,y1,x2,y2]的形式，描述格子(x1,y1)和格子(x2,y2)之间有障碍
ClmgFactory.prototype.addBarrier = function(_barrier)
{
    this.barriers.push(_barrier);
}

//判断某格元素是否为可移动元素
ClmgFactory.prototype.isMovableObj = function(x,y)
{
    //如果是字母，那么就是可移动元素
    if (this.board[y][x] >= 'A' && this.board[y][x] <= 'Z') {
        return true;
    }
    return false;
}

//判断是否越界
ClmgFactory.prototype.isCrossBoader = function(x,y)
{
    if (x < 0 || x >= this.width || y < 0 || y >= this.height) {
        return true;
    }
    return false;
}

//判断某格是否为可移动点
ClmgFactory.prototype.isMoveablePoint = function(x,y)
{
    //如果是绿地或者目标地，那么是可移动点
    if (this.board[y][x] == '1' || this.board[y][x] == '*') {
        return true;
    }
    return false;
}

//判断两格之间是否有障碍物
//_x1,_y1,_x2,_y2为两格的坐标
ClmgFactory.prototype.hasBarrier = function(_x1,_y1,_x2,_y2)
{
    for (let barrier of this.barriers) {
        if (barrier[0] == _x1 && barrier[1] == _y1 && barrier[2] == _x2 && barrier[3] == _y2) {
            return true;
        }
        if (barrier[0] == _x2 && barrier[1] == _y2 && barrier[2] == _x1 && barrier[3] == _y1) {
            return true;
        }
    }
    return false;
}



ClmgFactory.prototype.getMovePos = function(x,y,dir)
{
    let x2 = x;
    let y2 = y;
    switch (dir) {
        case 0: //右
            x2++;
            break;
        case 1: //上
            y2--;
            break;
        case 2: //左
            x2--;
            break;
        case 3: //下
            y2++;
            break;
    }
    let passed = !this.isCrossBoader(x2,y2);
    return [x2,y2,passed];
}

//尝试移动
//x,y: 可移动元素的坐标
//dir: 移动方向，0:上，1:下，2:左，3:右
ClmgFactory.prototype.tryMove = function(x,y,dir)
{
    //判断是否超出边界
    if(this.isCrossBoader(x,y)){
        return false;
    }
    //判断xy上是否有可移动元素
    if(!this.isMovableObj(x,y)){
        return false;
    }

    //现在开始移动
    let rtn = [false];
    let obj = this.board[y][x];
    if(obj == 'A'){
        rtn = this.moveA(x,y,dir);
    }
    if(obj == 'B'){
        rtn = this.moveB(x,y,dir);
    }
    if(obj == 'C'){
        rtn = this.moveC(x,y,dir);
    }
    if(obj == 'D'){
        rtn = this.moveD(x,y,dir);
    }
    if(obj == 'E'){
        rtn = this.moveE(x,y,dir);
    }
    if(obj == 'F'){
        rtn = this.moveF(x,y,dir);
    }
    if(obj == 'G'){
        rtn = this.moveG(x,y,dir);
    }

    if(rtn[0]){
        //检查限步是否足够
        let willConsume = rtn[3];
        if(!this.checkStepLimit(willConsume)){
            return false;
        }

        //移动A
        let xend = rtn[1];
        let yend = rtn[2];

        this.doMove(x,y,xend,yend,obj);
        let dirDescTable = ['右','上','左','下'];
        let animalTable = ['蜗牛','蜘蛛','蚂蚱','瓢虫','蜜蜂','蝴蝶','甲虫'];
        let animal = animalTable[obj.charCodeAt(0) - 'A'.charCodeAt(0)];
        this.actionDesc = `${x},${y}上的${obj}(${animal})向${dirDescTable[dir]}移动`; //动作描述
    }
    return rtn[0];
}

//检查地图限步能否完成
//_willConsume: 是否会消目的地
ClmgFactory.prototype.checkStepLimit = function(_willConsume)
{
    //统计目标点个数
     let count_target = 0;
    for (let i = 0; i < this.width; i++) {
        for (let j = 0; j < this.height; j++) {
            if (this.board[j][i] == '*') {
                count_target++;
            }
        }
    }
    //获得移动后的剩余步数
    let step_remain_after = this.step_limit - this.current_step - 1;
    //获得移动后的目标点数
    let count_target_after = count_target - (_willConsume ? 1 : 0);
    return step_remain_after >= count_target_after;
}



//检查地图合理性
ClmgFactory.prototype.checkBoard = function()
{
    //统计目标点的个数, 目标点的个数必须等于动物的个数
    let count_target = 0;
    let count_obj = 0;
    for (let i = 0; i < this.width; i++) {
        for (let j = 0; j < this.height; j++) {
            if (this.board[j][i] == '*') {
                count_target++;
            }
            if (this.board[j][i] >= 'A' && this.board[j][i] <= 'Z') {
                count_obj++;
            }
        }
    }
    return count_target == count_obj;
}

//执行move
ClmgFactory.prototype.doMove =function(x,y,x2,y2,obj)
{

    let target = this.board[y2][x2];
    this.board[y][x] = '1';
    if (target == '*') {
        //如果目标地是目标点，那么动物消失，目标地变绿地
        this.board[y2][x2] = '1';
    }else{
        if(obj == 'G'){
            //甲虫推动动物
            let objtest = this.board[y2][x2];
            this.board[y2][x2] = obj;
            if(objtest >= 'A' && objtest <= 'Z'){
                //推动的动物
                let dir = 0;
                if(x2 > x){
                    dir = 0;
                }else if(x2 < x){
                    dir = 2;
                }else if(y2 > y){
                    dir = 3;
                }else if(y2 < y){
                    dir = 1;
                }

                do{
                    let pos = this.getMovePos(x2,y2,dir);
                    if(!pos[2]){
                        //如果新坐标超出边界，那么不可移动
                        break;
                    }
                    x2 = pos[0];
                    y2 = pos[1];
                    let temp = objtest;
                    objtest = this.board[y2][x2];
                    if(objtest == '*'){
                        //如果目标地是目标点，那么动物消失，目标地变绿地
                        this.board[y2][x2] = '1';
                        break;
                    }
                    this.board[y2][x2] = temp;
                }
                while(objtest >= 'A' && objtest <= 'Z');

            }

            //this.board[y2][x2] = obj; //甲虫占据目标地
            //this.board[y][x] = '1'; //原位置变绿地}
        }else{
            //其他动物占据目标地
            this.board[y2][x2] = obj;
        }
    }
    //步数+1
    this.current_step++;

    //检查地图合理性
    if (!this.checkBoard()) {
        throw new Error('地图不合理');
    }
}


//尝试移动蜗牛
//蜗牛: 每次只能移动一步
//返回 [是否有解,xend,yend,是否会消目的地]
ClmgFactory.prototype.moveA =function(x,y,dir)
{
    let pos = this.getMovePos(x,y,dir);
    if(!pos[2]){
        //如果新坐标超出边界，那么不可移动
        return [false];
    }
    let xend = pos[0];
    let yend = pos[1];

    let obj2 = this.board[yend][xend];
    //如果新坐标不是绿地或者目标地，那么不可移动
    if(obj2 != '1' && obj2 != '*'){
        return [false];
    }
    //判断是否有障碍物
    if (this.hasBarrier(x,y,xend,yend)) {
        return [false];
    }
    //判断是否会消目的地
    let willConsume = obj2 == '*';
    return [true,xend,yend,willConsume];
}

//尝试移动蜘蛛
//蜘蛛: 一直往前移动，遇到障碍物和动物会停下来, 遇到空地会跌落失败;当停下来的时候，才会去判断是否到达目标地
//返回 [是否有解,xend,yend,是否会消目的地]
ClmgFactory.prototype.moveB = function(x,y,dir)
{
    if(x==2&&y==1&&dir==3){
        let debug = 1;
    }
    let xend = x;
    let yend = y;
    let obj = '';
    do{
        let pos = this.getMovePos(xend,yend,dir);
        if(!pos[2]){
            //如果新坐标超出边界，那么判断格子的边界是否有障碍物，有障碍物则停止移动，否则失败
            if(this.hasBarrier(xend,yend,pos[0],pos[1])){
                break;
            }else{
                return [false];
            }
        }
        let xt = pos[0];
        let yt = pos[1];
        let objt = this.board[yt][xt];
        //如果新坐标上有动物, 那么停止移动
        if(this.isMovableObj(xt,yt)) {
            break;
        }
        //判断两格之间是否有障碍物
        if (this.hasBarrier(xend,yend,xt,yt)) {
            break;
        }
        //如果新坐标上有空地, 那么跌落失败
        if(objt == '0') {
            return [false];
        }
        xend = xt;
        yend = yt;
        obj = objt;
    }while(true);
    
    if(xend == x && yend == y){
        return [false];
    }
    
    //判断是否会消目的地
    let willConsume = obj == '*';
    return [true,xend,yend,willConsume];
}

//尝试移动蚂蚱
//蚂蚱: 每次只能移动一步，如果遇到动物，则跳过去，可连续跳；遇到绿地或目标地则停止移动；
//      遇到空地或障碍物则失败
//返回 [是否有解,xend,yend,是否会消目的地]
ClmgFactory.prototype.moveC = function(x,y,dir)
{
    let xend = x;
    let yend = y;
    let obj = '';
    do{
        let pos = this.getMovePos(xend,yend,dir);
        if(!pos[2]){
            //如果新坐标超出边界，那么失败
            return [false];
        }
        let xt = pos[0];
        let yt = pos[1];
        let objt = this.board[yt][xt];
        //如果新坐标上有空地, 那么失败
        if(objt == '0') {
            return [false];
        }
        xend = xt;
        yend = yt;
        obj = objt;
        //遇到绿地停止移动
        if(objt == '1' || objt == '*'){
            break;
        }
    }while(true);
    
    //判断是否会消目的地
    let willConsume = obj == '*';
    return [true,xend,yend,willConsume];
}

//尝试移动瓢虫
//瓢虫: 每次只能移动两步，中间遇到阻碍或空地就停下来
//返回 [是否有解,xend,yend,是否会消目的地]
ClmgFactory.prototype.moveD = function(x,y,dir)
{
    let pos = this.getMovePos(x,y,dir);
    if(!pos[2]){
        //如果新坐标超出边界，那么失败
        return [false];
    }
    let xend = pos[0];
    let yend = pos[1];
    let obj = this.board[yend][xend];
    //判断两格之间是否有障碍物
    if (this.hasBarrier(x,y,xend,yend)) {
        return [false];
    }
    //如果新坐标上有动物，空地, 那么停止移动
    if(obj == '0' || this.isMovableObj(xend,yend)) {
        return [false];
    }
    let pos2 = this.getMovePos(xend,yend,dir);
    let x3 = pos2[0];
    let y3 = pos2[1];
    let x3y3_hasBarrier = this.hasBarrier(xend,yend,x3,y3);
    if(!pos2[2]){
        //如果超出边界
        if(!x3y3_hasBarrier){
            //如果没有障碍，那么失败
            return [false];
        }
    }else{
        let obj3 = this.board[y3][x3];
        //如果是空地那么失败
        if(obj3 == '0' && !x3y3_hasBarrier) {
            return [false];
        }
        //如果新坐标允许
        if((obj3 == '1' || obj3 == '*') && !x3y3_hasBarrier) {
            xend = x3;
            yend = y3;
            obj = obj3;
        }
    }
    
    //判断是否会消目的地
    let willConsume = obj == '*';
    return [true,xend,yend,willConsume];
}

//尝试移动蜜蜂
//蜜蜂: 每次只能移动两步，中间可越过阻碍或空地或动物；落脚点如果有动物则向前跳,可连续跳；
//返回 [是否有解,xend,yend,是否会消目的地]
ClmgFactory.prototype.moveE = function(x,y,dir)
{
    let pos = this.getMovePos(x,y,dir);
    if(!pos[2]){
        //如果新坐标超出边界，那么失败
        return [false];
    }
    let xend = pos[0];
    let yend = pos[1];
    let obj = this.board[yend][xend];

    do{
        let pos = this.getMovePos(xend,yend,dir);
        if(!pos[2]){
            //如果新坐标超出边界，那么失败
            return [false];
        }
        let xt = pos[0];
        let yt = pos[1];
        let objt = this.board[yt][xt];
        //如果新坐标上有空地, 那么失败
        if(objt == '0') {
            return [false];
        }
        xend = xt;
        yend = yt;
        obj = objt;
        //遇到绿地停止移动
        if(objt == '1' || objt == '*'){
            break;
        }
    }while(true);

    //判断是否会消目的地
    let willConsume = obj == '*';
    return [true,xend,yend,willConsume];
}

//尝试移动蝴蝶
//蝴蝶: 每次需要移动三步，中间可越过阻碍或空地或动物；落脚点如果有动物则向前跳,可连续跳；
//返回 [是否有解,xend,yend,是否会消目的地]
ClmgFactory.prototype.moveF = function(x,y,dir)
{
    let pos = this.getMovePos(x,y,dir);
    if(!pos[2]){
        //如果新坐标超出边界，那么失败
        return [false];
    }
    pos = this.getMovePos(pos[0],pos[1],dir);
    if(!pos[2]){
        //如果新坐标超出边界，那么失败
        return [false];
    }
    let xend = pos[0];
    let yend = pos[1];
    let obj = this.board[yend][xend];

    do{
        let pos = this.getMovePos(xend,yend,dir);
        if(!pos[2]){
            //如果新坐标超出边界，那么失败
            return [false];
        }
        let xt = pos[0];
        let yt = pos[1];
        let objt = this.board[yt][xt];
        //如果新坐标上有空地, 那么失败
        if(objt == '0') {
            return [false];
        }
        xend = xt;
        yend = yt;
        obj = objt;
        //遇到绿地停止移动
        if(objt == '1' || objt == '*'){
            break;
        }
    }while(true);

    //判断是否会消目的地
    let willConsume = obj == '*';
    return [true,xend,yend,willConsume];
}

//尝试移动甲虫
//甲虫: 每次只能移动一步，如果遇到动物，则推动动物前进一格
//返回 [是否有解,xend,yend,是否会消目的地]
ClmgFactory.prototype.moveG =function(x,y,dir)
{
    let pos = this.getMovePos(x,y,dir);
    if(!pos[2]){
        //如果新坐标超出边界，那么不可移动
        return [false];
    }
    let xend = pos[0];
    let yend = pos[1];
    let obj2 = this.board[yend][xend];
    //判断是否有障碍物
    if (this.hasBarrier(x,y,xend,yend)) {
        return [false];
    }
    let willConsume = false;
    if(this.isMovableObj(xend,yend)){
        //如果新坐标上有动物, 那么推动检查动物
        let pushRtn = this.CheckGPush(xend,yend,dir);
        if(!pushRtn[0]){
            //如果推动失败，那么不可移动
            return [false];
        }
        willConsume = pushRtn[1];
    }
    //如果新坐标不是绿地或者目标地，那么不可移动
    else if(obj2 != '1' && obj2 != '*'){
        return [false];
    }
    //判断是否会消目的地
    if(!willConsume){
        willConsume = obj2 == '*';
    }
    return [true,xend,yend,willConsume];
}

//检查甲虫推动,tx,ty为甲虫移动方向上的动物坐标
//返回 [是否能推动,是否会消目的地]
ClmgFactory.prototype.CheckGPush =function(tx,ty,dir)
{
    do{
        let pos = this.getMovePos(tx,ty,dir);
        if(!pos[2]){
            //如果新坐标超出边界，那么不可移动
            return [false];
        }
        let xend = pos[0];
        let yend = pos[1];
        let obj = this.board[yend][xend];
        //判断是否有障碍物
        if (this.hasBarrier(tx,ty,xend,yend)) {
            return [false];
        }
        //判断是否为空地
        if(obj == '0'){
            return [false];
        }
        //如果是绿地，那么可以推动
        if(obj == '1'){
            return [true,false];
        }
        //如果是目标地，那么可以推动
        if(obj == '*'){
            return [true,true];
        }
        //如果是动物，那么判断下一个格子
        tx = xend;
        ty = yend;
    }while(true);
}


ClmgFactory.prototype.getNextStates = function()
{
    let states = []
    //如果已经达到移动上限，那么不可移动
    if(this.current_step >= this.step_limit){
        return states;
    }
    for(let x = 0; x < this.width; x++)
    {
        for(let y = 0; y < this.height; y++)
        {
            //判断xy上是否有可移动元素
            if(!this.isMovableObj(x,y)){
                continue;
            }

            for (let i = 0; i < 4; i++)
            {
                let new_state = new ClmgFactory(0,0,0);
                new_state.CopyFrom(this);
                if (new_state.tryMove(x,y,i)) {
                    states.push(new_state);
                }
            }
        }
    }
    return states;
}

//判断两个节点是否相等
ClmgFactory.prototype.equal = function(node)
{
    if (this.id() != node.id()) {
        return false;
    }
    return true;
}

//
ClmgFactory.prototype.dump = function()
{
    let info = this.actionDesc + " : ";
    info += "step" + this.current_step;
    info += ",index" + this.index + "\n";
    if(this.oldboard && this.oldboard.length == this.height){
        for(let i=0;i<this.height;i++){
            info += this.oldboard[i].join('').replace(/0/g,' ') + "\n";
        }
    }
    info += '------ V ------\n';
    for(let i=0;i<this.height;i++){
        info += this.board[i].join('').replace(/0/g,' ') + "\n";
    }

    return info;
}

//判断是否到达目标状态
ClmgFactory.prototype.isGoal = function()
{
    //所有动物都消失
    for(let x = 0; x < this.width; x++)
    {
        for(let y = 0; y < this.height; y++)
        {
            if(this.isMovableObj(x,y)){
                return false;
            }
        }
    }
    return true;
}

//获得唯一标识
ClmgFactory.prototype.id = function() {
    //这里不使用hash,直接拼接状态
    let s;
    if(this.isGoal()){
        s = 'GOAL'; //保证所有的goal状态都是一致的
    }else{
        s = this.board.join('') + this.barriers.join(',');//+ this.current_step;
    }
    return s;
}

export { ClmgFactory };